package chapter_4.maxsubarray;

import sun.print.SunMinMaxPage;

/**
 * (MaxSubArray). 
 *
 * @author 汪文波(Wang Wenbo) wenboit@163.com
 * @notes Create on 2021-12-05 23:08
 */
public class Violent {

    public static void main(String[] args) {
        int[] arr = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
        int[] max = Violent.max(arr);
        // [43, 7, 10], 包含 7 和 10。
        System.out.printf("total: %d, index from %d to %d.", max[0], max[1], max[2]);
    }

    // 暴力破解法
    public static int[] max(int[] arr) {
        int[] result = new int[3];

        int total = 0;
        for (int startIndex = 0; startIndex < arr.length - 1; startIndex++) {
            int sum = 0;
            for (int endIndex = startIndex; endIndex < arr.length; endIndex++) {
                sum += arr[endIndex];
                if (sum > total) {
                    total = sum;
                    result[0] = total;
                    result[1] = startIndex;
                    result[2] = endIndex;
                }
            }
        }

        return result;
    }

}
